home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_07_08 / v7n8092b.txt < prev    next >
Text File  |  1988-12-20  |  7KB  |  239 lines
  1. /*------------------------------------------------------*/
  2. /*        Hsearch: Hash Table Manager             */
  3. /*                            */
  4. /*                            */
  5. /*  Usage:  call hcreate with the desired hash table    */ 
  6. /*         size                    */
  7. /*        call hsearch to enter and find items in the */
  8. /*           table                    */
  9. /*        call hdestroy when done (optional)        */
  10. /*        call hcount for number items in table    */
  11. /*        call hsize for size (# elements) of hash     */
  12. /*         table                    */
  13. /*        call hwrite to save hash table to disk    */
  14. /*        call hread to restore hash table from disk    */
  15. /*                            */
  16. /*  Restrictions:  Allows only one hash table to be     */
  17. /*                 open at the same time.        */
  18. /*  /Notes                          */
  19. /*       Uses fIND instead of FIND in subroutine    */
  20. /*       hashtable to avoid conflict with label FIND    */
  21. /*       in DOS.H.                    */
  22. /*                            */
  23. /*                            */
  24. /*  Programmer: T. Provenzano                  */
  25. /*        09/14/88      Original Version (in C)    */
  26. /*        10/07/88      Converted to C++    */
  27. /*                            */
  28. /*------------------------------------------------------*/
  29.  
  30. #include <string.h>
  31. #include <stdio.h>
  32. #include <dos.h>
  33. #include <io.h>
  34. #include <sys\stat.h>
  35. #include "search.hpp"
  36.  
  37. #define DEBUG
  38.  
  39. /*
  40.    The following macro allows debug statements without 
  41.    ifdef/endif obscuring the source code indentation
  42. */
  43. #ifdef DEBUG
  44. #define D(x) x
  45. #else
  46. #define D(x)
  47. #endif
  48.  
  49. /*--------------------------------------------------------*/
  50. /* Subroutine Prime calculates the greatest prime number 
  51.    less than or equal to the table size supplied by the 
  52.    caller.                              */
  53.  
  54. unsigned hashtable::prime(unsigned size)
  55. {
  56.   unsigned divisor;
  57.  
  58.   for (;; size--)
  59.   {
  60.     for (divisor=2; size % divisor != 0; divisor++)
  61.       ;
  62.     if (divisor == size) break;
  63.   }
  64.   D( printf("\nPrime number = %u\n", size); )
  65.   return size;
  66. }
  67. /*--------------------------------------------------------*/
  68. /* Subroutine hash implements the "division" technique
  69.    where the string characters are first summed and then 
  70.    divided (modulo) by the hash table size.    
  71.       f(X) = X mod M
  72.    X = identifier to hash; M = hash table size.              */
  73.  
  74. int hashtable::hash(char *str)
  75. {
  76.   int i=1, hash_val=0;
  77.  
  78.   for (; i <= strlen(str); i++)
  79.     hash_val += *str;
  80.   return (hash_val%num_elem);
  81. }
  82. /*--------------------------------------------------------*/
  83. /* fIND or ENTER an item in the hash table.  If a 
  84.    "collision" occurs sequential entries are searched in 
  85.    the table to find the next free slot.  The overflow item 
  86.    is ENTERed there or searches are made sequentially when 
  87.    FINDing a collided item.                      */
  88.  
  89. ENTRY* hashtable::hsearch(ENTRY item, ACTION action)
  90. {
  91.   int i, j;            // index into hash table
  92.   ENTRY *p;
  93.  
  94.   switch (action)
  95.   {
  96.     case ENTER:
  97.        i = j = hash(item.key);
  98.        D( printf("\nhash value = %d\n", i); )
  99.        p = (hash_table+i);
  100.        while (p->key != item.key && p->key != (char *)0 
  101.              && p->key != (char *)-1)
  102.        {
  103.      j++;
  104.      j %= num_elem;       // treat the table as circular
  105.      p = hash_table+j; // point to next slot in table
  106.          if (j == i)       // no room left in table!
  107.        return NULL;
  108.        }
  109.        /* insert info  */
  110.        p->key  = item.key;
  111.        p->data = item.data;
  112.        count++;            // one more in table 
  113.        D( printf("\nItem inserted at index %u\n", j); )
  114.        return p;
  115.     case fIND:
  116.        i = j = hash(item.key);
  117.        p = (hash_table+i);
  118.        while (strcmp(p->key, item.key) != 0)
  119.        {
  120.      j++;
  121.      j %= num_elem;    // treat the table as circular
  122.      p = hash_table+j; // point to next slot in table
  123.      // not in table
  124.          if (j == i || p->key == NULL) return NULL;       
  125.      if (p->key == (char *) -1) // skip DELETED entry 
  126.      {
  127.        j++;
  128.        j %= num_elem;    // treat table as circular      
  129.            p = hash_table+j;
  130.      }
  131.        }
  132.        return p;        // found item in table
  133.     case DELETE:
  134.        i = j = hash(item.key);
  135.        p = (hash_table+i);
  136.        while (strcmp(p->key, item.key) != 0)
  137.        {
  138.      j++;
  139.      j %= num_elem;        // treat table as circular
  140.      p = hash_table+j;    // next slot in table 
  141.      if (p->key == NULL) return NULL; // not in table
  142.        }
  143.        p->key  = p->data = (char *)-1;    // delete entry
  144.        count--;                // one less in table
  145.        D( printf("\nItem deleted at index %u\n", j); )
  146.        return p;
  147.     default:
  148.        D( printf("\nInvalid table operation\n"); )
  149.        return NULL;
  150.   }
  151. }
  152. /*--------------------------------------------------------*/
  153. /* Create a hash table.  Each entry in table consists of two
  154.    pointers: one to the ASCII key, the other to the data
  155.    associated with the key.  The hash table structure is
  156.    defined in the file "search.hpp".  If the memory for the
  157.    hash table is successfully allocated, the number of table
  158.    elements is returned; otherwise 0 is returned.
  159.              
  160.    Requested hash table size must be >= min_size.        */
  161.  
  162. int hashtable::hcreate(unsigned nel)
  163. {
  164.   const unsigned min_size = 25;
  165.   count = 0;            // init current table count 
  166.   if (nel < min_size) return 0;    // too small of a table!
  167.   // allocate memory for table
  168.   hash_table = new ENTRY[num_elem=prime(nel)];    
  169.   ENTRY *p = hash_table;
  170.   for (int i=0; i < num_elem; i++)    // zero hash table
  171.   {
  172.     p->key = p->data = (char *) 0;
  173.     p++;
  174.   }  
  175.   return ((hash_table==NULL) ? 0 : num_elem);
  176. }
  177. /*--------------------------------------------------------*/
  178. /* Destroy the hash table.  Must be done before another 
  179.    table can be created.                      */
  180.  
  181. void hashtable::hdestroy(void)
  182. {
  183.   delete hash_table;        // return the memory
  184.   return;
  185. }
  186. /*--------------------------------------------------------*/
  187. /* Return number of items currently in hash table         */
  188.  
  189. unsigned hashtable::hcount(void)
  190. {
  191.   return count;
  192. }
  193. /*--------------------------------------------------------*/
  194. /* Return hash table size                  */
  195.  
  196. unsigned hashtable::hsize(void)
  197. {
  198.   return num_elem;
  199. }
  200. /*--------------------------------------------------------*/
  201. /* Write hash table to disk.  Saves hash table in file 
  202.    "HASH.TBL" in current directory.  Returns success/fail 
  203.    status to caller.
  204.                                   */
  205. int hashtable::hwrite(void)
  206. {
  207.   unsigned int s, fd;
  208.   
  209.   fd = creat("HASH.TBL", S_IWRITE | S_IREAD);
  210.   if (fd == -1) return NULL;
  211.   s = write(fd, hash_table, sizeof(ENTRY)*num_elem);
  212.   close(fd);
  213.   return 1;
  214. }  
  215. /*--------------------------------------------------------*/
  216. /* Read hash table from disk.  Restores hash table in file 
  217.    "HASH.TBL" in current directory.  Returns success/fail 
  218.    status to caller.
  219.                                   */
  220. int hashtable::hread(void)
  221. {
  222.   unsigned int s, fd;
  223.   ENTRY *p=hash_table;
  224.   
  225.   count = 0;
  226.   fd = open("HASH.TBL", O_RDONLY);
  227.   if (fd == -1) return NULL;
  228.   s = read(fd, hash_table, sizeof(ENTRY)*num_elem);
  229.   for (int i=0; i < num_elem; i++)
  230.   {
  231.     if (p->key != (char *) -1 && p->key != (char *) 0) 
  232.       count++;
  233.     p++;
  234.   }  
  235.   D( printf("\nnumber of items read = %u\n", count); )    
  236.   close(fd);
  237.   return 1;
  238. }  
  239.